home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / 347_01.zip / TAVLTREE.DOC < prev    next >
Text File  |  1993-04-13  |  17KB  |  413 lines
  1. /*:file:version:date: "%n    V.%v;  %f"
  2.  * "TAVLTREE.DOC    V.3;  18-Feb-91,15:23:10"
  3.  *
  4.  *  Purpose: Documentation for TAVL library.
  5.  *
  6.  *      Copyright (c) 1991  Bert C. Hughes
  7.  *                          200 N.Saratoga
  8.  *                          St.Paul, MN 55104
  9.  *                          Compuserve 71211,577
  10.  */
  11.  
  12.  
  13.             ------------------------------------------------
  14.             TAVL library public functions, types & constants
  15.             ------------------------------------------------
  16.  
  17.                             ---------
  18.                             CONSTANTS
  19.                             ---------
  20.  
  21.      - Can be used as parameters for function tavl_insert -
  22. REPLACE ........ 1
  23. NO_REPLACE ..... 0
  24.  
  25.      - Return values of function tavl_setdata -
  26. TAVL_OK ........ 0  No error.
  27. TAVL_NOMEM ..... 1  Out of memory error.
  28. TAVL_ILLEGAL_OP  2  Requested operation would disrupt the
  29.                     tavl_tree structure; operation cancelled.
  30.  
  31.                                -----
  32.                                TYPES
  33.                                -----
  34.  
  35. TAVL_treeptr        Pointer to a TAVL tree.  Most tavl library
  36.                     functions require a TAVL_tree pointer as the
  37.                     first parameter.  A valid TAVL_treeptr can
  38.                     only be obtained via the function "tavl_init",
  39.                     which returns a TAVL_treeptr which can then be
  40.                     used as a parameter for other TAVL functions.
  41.                     All fields in *TAVL_treeptr are absolutely,
  42.                     unequivocally PRIVATE.  No point in even
  43.                     reading them.
  44.  
  45. TAVL_nodeptr        Pointer to a TAVL tree node.  Many TAVL functions
  46.                     require a TAVL_nodeptr as parameter, or return a
  47.                     TAVL_nodeptr.  Fields within *TAVL_nodeptr are
  48.                     PRIVATE - with one possible, but unnecessary,
  49.                     exception: TAVL_nodeptr->dataptr - in which case
  50.                     it is READONLY.
  51.                         Data should be obtained from a TAVL_nodeptr
  52.                     via the function "tavl_getdata", rather than
  53.                     reading "dataptr" directly.
  54.  
  55.  
  56.                         -----------------
  57.                             FUNCTIONS
  58.                         -----------------
  59.  
  60. TAVL_INIT
  61. ---------
  62.     purpose:        Creates a new TAVL tree. Returned pointer is used
  63.                     as a parameter to TAVL routines in subsequent
  64.                     processing.
  65.  
  66.     source file:    tavlinit.c
  67.     returns:        pointer to empty tree, or NULL if
  68.                     insufficient memory.
  69.  
  70.     prototype:      TAVL_treeptr tavl_init(
  71.                             int (*compare)(void *Key1, void *Key2),
  72.                             void *(*key_of)(void *DataObject),
  73.                             void *(*make_item)(const void *DataObject),
  74.                             void (*free_item)(void *DataObject),
  75.                             void *(*copy_item)(void *Dest_DataObject,
  76.                                          const void *Source_DataObject),
  77.                             void *(*alloc)(size_t),
  78.                             void (*dealloc)(void *)
  79.                     );
  80.  
  81.     parameters: All parameters for tavl_init are pointers to functions,
  82.                 so that you can tailor the behavior of the tavltree and
  83.                 the data it stores to fit the needs of your application.
  84.  
  85.                 compare   - Exclusively defines how the tavl library will
  86.                             make comparisons for this tree.
  87.                               must return:
  88.                                         0 - (Key1 == Key2)
  89.                                        >0 - (Key1 > Key2)
  90.                                        <0 - (Key1 < Key2)
  91.  
  92.                 key_of    - Must return a pointer to the identifier of
  93.                             data objects which are being inserted into
  94.                             this instance of tavl tree. Within the TAVL
  95.                             library, result of the "key_of" function is
  96.                             passed directly to the "compare" function.
  97.  
  98.                             (Identifier - that which distinguishes this
  99.                             data object from other data objects.
  100.                             Its "name".)
  101.  
  102.                 make_item - Must create a copy of the data object passed
  103.                             to it. This function is also responsible for
  104.                             allocating memory necessary for storing the
  105.                             copy of the data object.  Library function
  106.                             tavl_insert uses "make_item" to make a copy
  107.                             of the item, or object, to insert into the
  108.                             tree, and library function tavl_setdata uses
  109.                             "make_item" to create a copy of the data
  110.                             item passed to it.
  111.  
  112.                 free_item - Opposite of make_item. Function "free_item"
  113.                             must free or deallocate memory given to
  114.                             the object by "make_item".
  115.  
  116.                 copy_item - Copies a data object to a buffer.  All memory
  117.                             necessary to store the object must have been
  118.                             allocated before "copy_item" is called.
  119.  
  120.                 alloc     - A memory allocator for the tavl library to
  121.                             use for its private purposes, ie, allocation
  122.                             of nodes and struct tavltree.
  123.  
  124.                 dealloc   - Counterpart to "alloc".
  125.  
  126.                   Often "alloc" & "dealloc" will be the complementary
  127.                   C library functions "malloc" and "free".
  128.  
  129.  
  130.  
  131. TAVL_INSERT
  132. -----------
  133.    purpose:     Inserts data objects into the tree.
  134.  
  135.    source file: tavl_ins.c
  136.  
  137.    returns:     A pointer to the node which contains the data object
  138.                 inserted or found.
  139.  
  140.    prototype:   TAVL_nodeptr tavl_insert(
  141.                                 TAVL_treeptr tree,
  142.                                 void        *item,
  143.                                 int          replace
  144.                                 );
  145.  
  146.    parameters:  tree -      Pointer to the tree into which data will be
  147.                             inserted.
  148.  
  149.                 item -      Pointer to the object to insert.
  150.  
  151.                 replace -   Instructs "tavl_insert" on how to behave
  152.                             if the tree already contains a data object
  153.                             whose identifier equals key_of(item).
  154.                             If replace != 0, the new data object will
  155.                             replace the old, otherwise nothing happens,
  156.                             tavl_insert simply returns a pointer to
  157.                             the found node.
  158.  
  159.     NOTES:      "tavl_insert" requires the private function
  160.                 "rebalance_tavl" contained in source file "tavlrebl.c",
  161.                 so the module "tavlrebl.obj" (or whatever, depending on
  162.                 your system) must be linked to the final executable
  163.                 program.
  164.  
  165.  
  166. TAVL_DELETE
  167. -----------
  168.     purpose:        Deletes node containing item such that
  169.                     *key_of(node.item) == *key.
  170.  
  171.     source file:    tavl_del.c
  172.  
  173.     returns:        1 if successful, otherwise 0.
  174.  
  175.     prototype:      int tavl_delete(TAVL_treeptr tree, void *key);
  176.  
  177.     parameters:     tree -  Tree to remove object from.
  178.                     key  -  Identifier of object to remove.
  179.  
  180.     NOTES:      "tavl_delete" requires the private function
  181.                 "rebalance_tavl" contained in source file "tavlrebl.c",
  182.                 so the module "tavlrebl.obj" (or whatever, depending on
  183.                 your system) must be linked to the final executable
  184.                 program.
  185.  
  186.  
  187.  
  188. TAVL_FIND
  189. ---------
  190.     purpose:        Find node whose data object's identifier
  191.                     equals *key.
  192.  
  193.     source file:    tavlfind.c
  194.  
  195.     prototype:      TAVL_nodeptr tavl_find(TAVL_treeptr tree, void *key);
  196.  
  197.     parameters:     tree -  Tree to search.
  198.                     key  -  Identifier of object to find.
  199.  
  200.  
  201.  
  202.  
  203. TAVL_GETDATA        source file: tavl_gdt.c
  204. ------------
  205.     purpose:        Copies data object contained in *p to *buffer.
  206.                     Uses function "copy_item" to accomplish its
  207.                     mission; see tavl_init.
  208.  
  209.     returns:        Result of function "copy_item"; if all is OK,
  210.                     this should be a void pointer to parameter "buffer",
  211.                     but definition of "copy_item" is left to
  212.                     the TAVL-library user.
  213.  
  214.     prototype:      void *tavl_getdata(
  215.                             TAVL_treeptr tree,
  216.                             TAVL_nodeptr p,
  217.                             void *buffer);
  218.  
  219.  
  220.  
  221.  
  222. TAVL_SETDATA        source file: tavl_sdt.c
  223. ------------
  224.     purpose:        Directly replace the data object contained in
  225.                     node "p".  Fails if identifier of object in
  226.                     node "p" does not equal identifier of "item".
  227.                     NOTE: this function has same effect as
  228.                     "tavl_insert(tree,item,REPLACE)" where it is
  229.                     known that an object exists in the tree such
  230.                     that *key_of(item) == *key_of(existing_object).
  231.  
  232.  
  233.     returns:        if successful   ........... TAVL_OK
  234.                     if insufficient memory .... TAVL_NOMEM
  235.                     if illegal operation ...... TAVL_ILLEGAL_OP,
  236.                       where an illegal operation is either
  237.                       trying to set data on the head node
  238.                       (returned by tavl_reset), or trying
  239.                       to replace the existing data object
  240.                       with an object whose identifier is
  241.                       not equal to the original object's
  242.                       identifier.
  243.  
  244.     prototype:      int tavl_setdata(
  245.                             TAVL_treeptr tree,
  246.                             TAVL_nodeptr p,
  247.                             void *item);
  248.  
  249.     parameters:     tree -  Pointer to the tree in question.
  250.                     p    -  Pointer to the node containing
  251.                             object to replace.
  252.                     item -  Pointer to replacement item.
  253.  
  254.  
  255.  
  256.  
  257. TAVL_DELETE_ALL     source file: tavldall.c
  258. ---------------
  259.     purpose:        Remove all data nodes from the tree and
  260.                     release memory used by those nodes.
  261.  
  262.     prototype:      void tavl_delete_all(TAVL_treeptr tree);
  263.  
  264.     NOTES:      "tavl_delete_all" uses TAVL library functions
  265.                 "tavl_reset" and "tavl_succ", so these
  266.                 modules must be linked to the final executable.
  267.  
  268.  
  269.  
  270.  
  271. TAVL_DESTROY        source file:    tavlfree.c
  272. ------------
  273.     purpose:        Release all memory used by the tree and
  274.                     its data nodes; i.e., destroy the tree.
  275.  
  276.     prototype:      void tavl_destroy(TAVL_treeptr tree);
  277.  
  278.     NOTES:      "tavl_destroy" uses TAVL library functions
  279.                 "tavl_reset" and "tavl_succ", so these
  280.                 modules must be linked to the final executable.
  281.  
  282.  
  283.  
  284.   --------------------------------------------------------------------
  285.   | Following three functions allow you to treat tavl_trees as a     |
  286.   | doubly linked sorted list with a head node.  This is the point   |
  287.   | of threaded trees - it is almost as efficient to move from node  |
  288.   | to node or back with a threaded tree as it is with a linked list.|
  289.   --------------------------------------------------------------------
  290.  
  291.  
  292. TAVL_RESET          source file: tavl_rst.c
  293. ----------
  294.     purpose:        Used in conjunction with "tavl_succ" & "tavl_pred",
  295.                     "tavl_reset" returns a pointer to the head node
  296.                     of the tree. The head node contains no data,
  297.                     rather it is the begin/end of the tree viewed as
  298.                     a sorted doubly linked circular list. Subsequent
  299.                     call to "tavl_succ"/"tavl_pred" returns first/last
  300.                     (or least/greatest) node of this list.
  301.  
  302.     prototype:      TAVL_nodeptr tavl_reset(TAVL_treeptr tree);
  303.  
  304.  
  305.  
  306. TAVL_SUCC           source file: tavlsucc.c
  307. ---------
  308.     purpose:        Returns pointer to node that is the in-order
  309.                     successor of node p, or NULL if p is last
  310.                     element in the list (head doesn't count).
  311.                     Input parameter "p" may be obtained from
  312.                     the functions "tavl_reset", "tavl_find",
  313.                     "tavl_insert", or "tavl_pred".
  314.  
  315.     prototype:      TAVL_nodeptr tavl_succ(TAVL_nodeptr p);
  316.  
  317.  
  318.  
  319. TAVL_PRED           source file: tavlpred.c
  320. ---------
  321.     purpose:        Returns in-order predecessor of "p";
  322.                     almost the inverse of tavl_succ. I.e.,
  323.  
  324.                        p == tavl_pred(tavl_succ(p))
  325.                     and
  326.                        p == tavl_succ(tavl_pred(p))
  327.  
  328.                     EXCEPT! when the inner function in
  329.                     the relationship above returns NULL
  330.                     because it has reached begin/end of
  331.                     the list (tree).
  332.  
  333.     prototype:      TAVL_nodeptr tavl_pred(TAVL_nodeptr p);
  334.  
  335.  
  336. /****************************************************************************/
  337. /*                  PRIVATE STUFF - FOR USE OF TAVL-LIBRARY ONLY            */
  338. /*                  but it's here anyway because C programmers              */
  339. /*                  want to know...                                         */
  340. /****************************************************************************/
  341.  
  342. function:
  343.  
  344. REBALANCE_TAVL      source-file: tavlrebl.c
  345. --------------
  346.  
  347.     purpose:        Used internally by the "tavl_insert"
  348.                     and "tavl_delete" functions.  Should
  349.                     NEVER, EVER, be called by an application.
  350.                     But if it was, it wouldn't harm anything -
  351.                     since the tree is always balanced at application
  352.                     level, a call to rebalance would simply return
  353.                     with no changes or actions taken.
  354.  
  355.     prototype:      In source file "tavlpriv.h", which must be present
  356.                     when compiling TAVL library routines.
  357.  
  358.  
  359. types:
  360.  
  361. typedef struct tavlnode {
  362.             void *dataptr;
  363.             struct tavlnode *Lptr, *Rptr;
  364.             signed   int bf     : 3;    /* assumes values -2..+2 */
  365.             unsigned int Lbit   : 1;
  366.             unsigned int Rbit   : 1;
  367.         } TAVL_NODE, *TAVL_nodeptr;
  368.  
  369.     fields:
  370.  
  371.     dataptr:
  372.             Pointer to the data object stored in this node.
  373.  
  374.     Lptr,Rptr:
  375.             Pointers to either left/right child trees, or predecessor/
  376.             successor nodes, depending on state of Lbit, Rbit flags.
  377.  
  378.     bf:     In a balanced tree, -1 <= bf <= +1.  When inserting or deleting,
  379.             bf may become == abs(2); this signals these routines that the
  380.             tree must be rebalanced, starting at the unbalanced node.
  381.  
  382.     Lbit,Rbit:
  383.             Flags that determine if Rptr, Lptr are links to child trees
  384.             or threads to in-order predecessor/successor nodes.
  385.  
  386.  
  387. typedef struct tavltree {
  388.             TAVL_nodeptr head;
  389.             int (*cmp)(void *, void *);
  390.             void *(*key_of)(void *);
  391.             void *(*make_item)(const void *);
  392.             void (*free_item)(void *);
  393.             void *(*copy_item)(void *, const void *);
  394.             void *(*alloc)(size_t);
  395.             void (*dealloc)(void *);
  396.         } TAVL_TREE, *TAVL_treeptr;
  397.  
  398.  
  399.     fields: "head" is a non-data node created at initialization;
  400.             algorithms dealing with the tree are simplified by
  401.             its presence. "head" is also the pointer returned
  402.             by the TAVL-library function "tavl_reset", and serves
  403.             as a marker to begin/end of the tree-as-sorted-list.
  404.  
  405.             All the other fields are function pointers set at
  406.             initialization time; see "tavl_init".  TAVL library
  407.             routines perform the functions named by these functions
  408.             exclusively through the use of these function pointers.
  409.  
  410. /*****************************************************************************/
  411. /*                               THE END                                     */
  412. /*****************************************************************************/
  413.